package Intermediate_algorithm.SortAndSearch;

import org.junit.Test;

/*
在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回[-1, -1]。
你必须设计并实现时间复杂度为O(log n)x的算法解决此问题。

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/binary-search/xenp13/
 */
public class _05在排序数组中查找元素的第一个和最后一个位置 {

    @Test
    public void test() {
        searchRange(new int[]{2,2},3);
    }

    //先二分查找  再遍历
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return new int[]{-1,-1};
        int[] res = new int[2];
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                left = mid;
                right = mid;
                break;
            }else if (nums[mid] < target) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        if(left != right){
            return new int[]{-1,-1};
        }else {
            while (left - 1 >= 0 && nums[left - 1] == target) {
                left--;
            }
            while (right + 1 < n && nums[right + 1] == target) {
                right++;
            }
            res[0] = left;
            res[1] = right;
        }
        return res;
    }

}
